package org.example.leetcpde;

import org.junit.jupiter.api.Test;

import java.util.*;

public class letterCombinations {

    @Test
    void ab() {
        String aa = "23";
        List<String> strings = letterCombinations(aa);
        for (String string : strings) {
            System.out.println(string);
        }
    }

    public List<String> letterCombinations(String digits) {
        if (digits == null || digits.length() == 0) {
            return Collections.emptyList();
        }

        Map<Character, Character[]> map = new HashMap<>(){{
            put('2', new Character[]{'a', 'b', 'c'});
            put('3', new Character[]{'d', 'e', 'f'});
            put('4', new Character[]{'g', 'h', 'i'});
            put('5', new Character[]{'j', 'k', 'l'});
            put('6', new Character[]{'m', 'n', 'o'});
            put('7', new Character[]{'p', 'q', 'r', 's'});
            put('8', new Character[]{'t', 'u', 'v'});
            put('9', new Character[]{'w', 'x', 'y', 'z'});
        }};

        char[] chars = digits.toCharArray();
        int len = chars.length;
        List<String> res = new ArrayList<>();
        dfs(new StringBuilder(), res, map, 0, chars, len);
        return res;
    }

    void dfs(StringBuilder builder,
             List<String> res,
             Map<Character, Character[]> map,
             int idx,
             char[] chars,
             int n) {
        if (builder.length() == n) {
            res.add(builder.toString());
            return;
        }


        for (Character choice : map.get(chars[idx])) {
            builder.append(choice);
            dfs(builder, res, map, idx + 1, chars, n);
            builder.deleteCharAt(builder.length() - 1);
        }
    }
}
